
public class MinHeap extends Heap{
	
	public MinHeap(int size){
		super(size);
	}
	
	public void Insert(int value){
		if(nextIndex < dataArray.length)
		{
			int index = nextIndex;
			dataArray[index] = value;
			nextIndex++;
			
			while(index >= 0 && dataArray[index] < dataArray[(index - 1)/2])
			{
				int temp = dataArray[index];
				dataArray[index] = dataArray[(index - 1)/2];
				dataArray[(index - 1)/2] = temp;
				index = (index - 1)/2;
			}
		}
	}
	
	public int ExtractMin(){
		return ExtractRoot();
	}

	
	private int GetMinChildIndex(int index){
		
		int leftChildIndex = index * 2 + 1;
		int rightChildIndex = index * 2 + 2;
		if(leftChildIndex < nextIndex)
		{
			if(rightChildIndex < nextIndex)
			{
				if(dataArray[index] > dataArray[leftChildIndex] && dataArray[rightChildIndex] > dataArray[leftChildIndex])
				{
					return leftChildIndex;
				}
				else if(dataArray[index] > dataArray[rightChildIndex] && dataArray[leftChildIndex] > dataArray[rightChildIndex])
				{
					return rightChildIndex;
				}
			}
			else if(dataArray[index] > dataArray[leftChildIndex])
			{
				return leftChildIndex;
			}
		}
		
		return -1;
	}
	
	
	public  void DeleteRoot(){
		dataArray[0] = dataArray[--nextIndex];
		
		int index = 0;
		
		while(index < nextIndex)
		{
			int minIndex = GetMinChildIndex(index);
			
			if(minIndex == -1)
				break;
			
			int temp = dataArray[index];
			dataArray[index] = dataArray[minIndex];
			dataArray[minIndex] = temp;
			index = minIndex;
		}
	}
}
